class Solution:
    def maximalSquare(self, matrix) -> int:
        dp = [[int(y) for y in x] for x in matrix]
        for i in range(1, len(matrix)):
            for j in range(1, len(matrix[i])):
                if matrix[i][j] == '1' and dp[i - 1][j - 1] >= 1:
                    maxLen = dp[i - 1][j - 1]
                    for k in range(i - 1, i - 1 - maxLen, -1):
                        if matrix[k][j] == '0':
                            maxLen = i - 1 - k
                            break
                    for k in range(j - 1, j - 1 - maxLen, -1):
                        if matrix[i][k] == '0':
                            maxLen = j - 1 - k
                            break
                    dp[i][j] = 1 + maxLen

        maxLen = 0
        for i in dp:
            for j in i:
                maxLen = max(j, maxLen)
        return maxLen**2


if __name__ == '__main__':
    so = Solution()
    s = """
0 1 1 1
1 1 1 1
0 1 1 1"""
    s = s[1:]
    s = s.split("\n")
    s = [x.split(" ") for x in s]
    # s = [[int(y) for y in x] for x in s]
    print(s)
    r = so.maximalSquare(s)
    print(r)
